/*
 * Copyright (C) 2007 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.base.Predicate;
import com.google.common.base.Predicates;
import com.google.common.collect.Collections2.FilteredCollection;
import com.google.common.math.IntMath;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import java.io.Serializable;
import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.NavigableSet;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArraySet;
import java.util.stream.Collector;
import java.util.stream.Stream;
import javax.annotation.Nullable;

/**
 * Static utility methods pertaining to {@link Set} instances. Also see this class's counterparts
 * {@link Lists}, {@link Maps} and {@link Queues}.
 *
 * <p>
 * See the Guava User Guide article on
 * <a href= "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#sets">
 * {@code Sets}</a>.
 *
 * @author Kevin Bourrillion
 * @author Jared Levy
 * @author Chris Povirk
 * @since 2.0
 */
@GwtCompatible(emulated = true)
public final class Sets {
    private Sets() {}

    /**
     * {@link AbstractSet} substitute without the potentially-quadratic {@code removeAll}
     * implementation.
     */
    abstract static class ImprovedAbstractSet<E> extends AbstractSet<E> {
        @Override
        public boolean removeAll(Collection<?> c) {
            return removeAllImpl(this, c);
        }

        @Override
        public boolean retainAll(Collection<?> c) {
            return super.retainAll(checkNotNull(c)); // GWT compatibility
        }
    }

    /**
     * Returns an immutable set instance containing the given enum elements. Internally, the
     * returned set will be backed by an {@link EnumSet}.
     *
     * <p>
     * The iteration order of the returned set follows the enum's iteration order, not the order in
     * which the elements are provided to the method.
     *
     * @param anElement one of the elements the set should contain
     * @param otherElements the rest of the elements the set should contain
     * @return an immutable set containing those elements, minus duplicates
     */
    // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
    @GwtCompatible(serializable = true)
    public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(E anElement, E... otherElements) {
        return ImmutableEnumSet.asImmutable(EnumSet.of(anElement, otherElements));
    }

    /**
     * Returns an immutable set instance containing the given enum elements. Internally, the
     * returned set will be backed by an {@link EnumSet}.
     *
     * <p>
     * The iteration order of the returned set follows the enum's iteration order, not the order in
     * which the elements appear in the given collection.
     *
     * @param elements the elements, all of the same {@code enum} type, that the set should contain
     * @return an immutable set containing those elements, minus duplicates
     */
    // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028
    @GwtCompatible(serializable = true)
    public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet(Iterable<E> elements) {
        if (elements instanceof ImmutableEnumSet) {
            return (ImmutableEnumSet<E>) elements;
        } else if (elements instanceof Collection) {
            Collection<E> collection = (Collection<E>) elements;
            if (collection.isEmpty()) {
                return ImmutableSet.of();
            } else {
                return ImmutableEnumSet.asImmutable(EnumSet.copyOf(collection));
            }
        } else {
            Iterator<E> itr = elements.iterator();
            if (itr.hasNext()) {
                EnumSet<E> enumSet = EnumSet.of(itr.next());
                Iterators.addAll(enumSet, itr);
                return ImmutableEnumSet.asImmutable(enumSet);
            } else {
                return ImmutableSet.of();
            }
        }
    }

    private static final class Accumulator<E extends Enum<E>> {
        static final Collector<Enum<?>, ?, ImmutableSet<? extends Enum<?>>> TO_IMMUTABLE_ENUM_SET =
                (Collector) Collector.<Enum, Accumulator, ImmutableSet<?>>of(Accumulator::new, Accumulator::add,
                        Accumulator::combine, Accumulator::toImmutableSet, Collector.Characteristics.UNORDERED);

        private EnumSet<E> set;

        void add(E e) {
            if (set == null) {
                set = EnumSet.of(e);
            } else {
                set.add(e);
            }
        }

        Accumulator<E> combine(Accumulator<E> other) {
            if (this.set == null) {
                return other;
            } else if (other.set == null) {
                return this;
            } else {
                this.set.addAll(other.set);
                return this;
            }
        }

        ImmutableSet<E> toImmutableSet() {
            return (set == null) ? ImmutableSet.<E>of() : ImmutableEnumSet.asImmutable(set);
        }
    }

    /**
     * Returns a {@code Collector} that accumulates the input elements into a new
     * {@code ImmutableSet} with an implementation specialized for enums. Unlike
     * {@link ImmutableSet#toImmutableSet}, the resulting set will iterate over elements in their
     * enum definition order, not encounter order.
     *
     * @since 21.0
     */
    @Beta
    public static <E extends Enum<E>> Collector<E, ?, ImmutableSet<E>> toImmutableEnumSet() {
        return (Collector) Accumulator.TO_IMMUTABLE_ENUM_SET;
    }

    /**
     * Returns a new, <i>mutable</i> {@code EnumSet} instance containing the given elements in their
     * natural order. This method behaves identically to {@link EnumSet#copyOf(Collection)}, but
     * also accepts non-{@code Collection} iterables and empty iterables.
     */
    public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable, Class<E> elementType) {
        EnumSet<E> set = EnumSet.noneOf(elementType);
        Iterables.addAll(set, iterable);
        return set;
    }

    // HashSet

    /**
     * Creates a <i>mutable</i>, initially empty {@code HashSet} instance.
     *
     * <p>
     * <b>Note:</b> if mutability is not required, use {@link ImmutableSet#of()} instead. If
     * {@code E} is an {@link Enum} type, use {@link EnumSet#noneOf} instead. Otherwise, strongly
     * consider using a {@code LinkedHashSet} instead, at the cost of increased memory footprint, to
     * get deterministic iteration behavior.
     *
     * <p>
     * <b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as
     * deprecated. Instead, use the {@code HashSet} constructor directly, taking advantage of the
     * new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
     */
    public static <E> HashSet<E> newHashSet() {
        return new HashSet<E>();
    }

    /**
     * Creates a <i>mutable</i> {@code HashSet} instance initially containing the given elements.
     *
     * <p>
     * <b>Note:</b> if elements are non-null and won't be added or removed after this point, use
     * {@link ImmutableSet#of()} or {@link ImmutableSet#copyOf(Object[])} instead. If {@code E} is
     * an {@link Enum} type, use {@link EnumSet#of(Enum, Enum[])} instead. Otherwise, strongly
     * consider using a {@code LinkedHashSet} instead, at the cost of increased memory footprint, to
     * get deterministic iteration behavior.
     *
     * <p>
     * This method is just a small convenience, either for {@code newHashSet(}{@link Arrays#asList
     * asList}{@code (...))}, or for creating an empty set then calling {@link Collections#addAll}.
     * This method is not actually very useful and will likely be deprecated in the future.
     */
    public static <E> HashSet<E> newHashSet(E... elements) {
        HashSet<E> set = newHashSetWithExpectedSize(elements.length);
        Collections.addAll(set, elements);
        return set;
    }

    /**
     * Returns a new hash set using the smallest initial table size that can hold
     * {@code expectedSize} elements without resizing. Note that this is not what
     * {@link HashSet#HashSet(int)} does, but it is what most users want and expect it to do.
     *
     * <p>
     * This behavior can't be broadly guaranteed, but has been tested with OpenJDK 1.7 and 1.8.
     *
     * @param expectedSize the number of elements you expect to add to the returned set
     * @return a new, empty hash set with enough capacity to hold {@code expectedSize} elements
     *         without resizing
     * @throws IllegalArgumentException if {@code expectedSize} is negative
     */
    public static <E> HashSet<E> newHashSetWithExpectedSize(int expectedSize) {
        return new HashSet<E>(Maps.capacity(expectedSize));
    }

    /**
     * Creates a <i>mutable</i> {@code HashSet} instance containing the given elements. A very thin
     * convenience for creating an empty set then calling {@link Collection#addAll} or
     * {@link Iterables#addAll}.
     *
     * <p>
     * <b>Note:</b> if mutability is not required and the elements are non-null, use
     * {@link ImmutableSet#copyOf(Iterable)} instead. (Or, change {@code elements} to be a
     * {@link FluentIterable} and call {@code elements.toSet()}.)
     *
     * <p>
     * <b>Note:</b> if {@code E} is an {@link Enum} type, use {@link #newEnumSet(Iterable, Class)}
     * instead.
     *
     * <p>
     * <b>Note for Java 7 and later:</b> if {@code elements} is a {@link Collection}, you don't need
     * this method. Instead, use the {@code HashSet} constructor directly, taking advantage of the
     * new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
     *
     * <p>
     * Overall, this method is not very useful and will likely be deprecated in the future.
     */
    public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) {
        return (elements instanceof Collection) ? new HashSet<E>(Collections2.cast(elements))
                : newHashSet(elements.iterator());
    }

    /**
     * Creates a <i>mutable</i> {@code HashSet} instance containing the given elements. A very thin
     * convenience for creating an empty set and then calling {@link Iterators#addAll}.
     *
     * <p>
     * <b>Note:</b> if mutability is not required and the elements are non-null, use
     * {@link ImmutableSet#copyOf(Iterator)} instead.
     *
     * <p>
     * <b>Note:</b> if {@code E} is an {@link Enum} type, you should create an {@link EnumSet}
     * instead.
     *
     * <p>
     * Overall, this method is not very useful and will likely be deprecated in the future.
     */
    public static <E> HashSet<E> newHashSet(Iterator<? extends E> elements) {
        HashSet<E> set = newHashSet();
        Iterators.addAll(set, elements);
        return set;
    }

    /**
     * Creates a thread-safe set backed by a hash map. The set is backed by a
     * {@link ConcurrentHashMap} instance, and thus carries the same concurrency guarantees.
     *
     * <p>
     * Unlike {@code HashSet}, this class does NOT allow {@code null} to be used as an element. The
     * set is serializable.
     *
     * @return a new, empty thread-safe {@code Set}
     * @since 15.0
     */
    public static <E> Set<E> newConcurrentHashSet() {
        return Collections.newSetFromMap(new ConcurrentHashMap<E, Boolean>());
    }

    /**
     * Creates a thread-safe set backed by a hash map and containing the given elements. The set is
     * backed by a {@link ConcurrentHashMap} instance, and thus carries the same concurrency
     * guarantees.
     *
     * <p>
     * Unlike {@code HashSet}, this class does NOT allow {@code null} to be used as an element. The
     * set is serializable.
     *
     * @param elements the elements that the set should contain
     * @return a new thread-safe set containing those elements (minus duplicates)
     * @throws NullPointerException if {@code elements} or any of its contents is null
     * @since 15.0
     */
    public static <E> Set<E> newConcurrentHashSet(Iterable<? extends E> elements) {
        Set<E> set = newConcurrentHashSet();
        Iterables.addAll(set, elements);
        return set;
    }

    // LinkedHashSet

    /**
     * Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance.
     *
     * <p>
     * <b>Note:</b> if mutability is not required, use {@link ImmutableSet#of()} instead.
     *
     * <p>
     * <b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as
     * deprecated. Instead, use the {@code LinkedHashSet} constructor directly, taking advantage of
     * the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
     *
     * @return a new, empty {@code LinkedHashSet}
     */
    public static <E> LinkedHashSet<E> newLinkedHashSet() {
        return new LinkedHashSet<E>();
    }

    /**
     * Creates a {@code LinkedHashSet} instance, with a high enough "initial capacity" that it
     * <i>should</i> hold {@code expectedSize} elements without growth. This behavior cannot be
     * broadly guaranteed, but it is observed to be true for OpenJDK 1.7. It also can't be
     * guaranteed that the method isn't inadvertently <i>oversizing</i> the returned set.
     *
     * @param expectedSize the number of elements you expect to add to the returned set
     * @return a new, empty {@code LinkedHashSet} with enough capacity to hold {@code expectedSize}
     *         elements without resizing
     * @throws IllegalArgumentException if {@code expectedSize} is negative
     * @since 11.0
     */
    public static <E> LinkedHashSet<E> newLinkedHashSetWithExpectedSize(int expectedSize) {
        return new LinkedHashSet<E>(Maps.capacity(expectedSize));
    }

    /**
     * Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the given elements in
     * order.
     *
     * <p>
     * <b>Note:</b> if mutability is not required and the elements are non-null, use
     * {@link ImmutableSet#copyOf(Iterable)} instead.
     *
     * <p>
     * <b>Note for Java 7 and later:</b> if {@code elements} is a {@link Collection}, you don't need
     * this method. Instead, use the {@code LinkedHashSet} constructor directly, taking advantage of
     * the new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
     *
     * <p>
     * Overall, this method is not very useful and will likely be deprecated in the future.
     *
     * @param elements the elements that the set should contain, in order
     * @return a new {@code LinkedHashSet} containing those elements (minus duplicates)
     */
    public static <E> LinkedHashSet<E> newLinkedHashSet(Iterable<? extends E> elements) {
        if (elements instanceof Collection) {
            return new LinkedHashSet<E>(Collections2.cast(elements));
        }
        LinkedHashSet<E> set = newLinkedHashSet();
        Iterables.addAll(set, elements);
        return set;
    }

    // TreeSet

    /**
     * Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the natural sort ordering
     * of its elements.
     *
     * <p>
     * <b>Note:</b> if mutability is not required, use {@link ImmutableSortedSet#of()} instead.
     *
     * <p>
     * <b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as
     * deprecated. Instead, use the {@code TreeSet} constructor directly, taking advantage of the
     * new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
     *
     * @return a new, empty {@code TreeSet}
     */
    public static <E extends Comparable> TreeSet<E> newTreeSet() {
        return new TreeSet<E>();
    }

    /**
     * Creates a <i>mutable</i> {@code TreeSet} instance containing the given elements sorted by
     * their natural ordering.
     *
     * <p>
     * <b>Note:</b> if mutability is not required, use {@link ImmutableSortedSet#copyOf(Iterable)}
     * instead.
     *
     * <p>
     * <b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit comparator, this
     * method has different behavior than {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code
     * TreeSet} with that comparator.
     *
     * <p>
     * <b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as
     * deprecated. Instead, use the {@code TreeSet} constructor directly, taking advantage of the
     * new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
     *
     * <p>
     * This method is just a small convenience for creating an empty set and then calling
     * {@link Iterables#addAll}. This method is not very useful and will likely be deprecated in the
     * future.
     *
     * @param elements the elements that the set should contain
     * @return a new {@code TreeSet} containing those elements (minus duplicates)
     */
    public static <E extends Comparable> TreeSet<E> newTreeSet(Iterable<? extends E> elements) {
        TreeSet<E> set = newTreeSet();
        Iterables.addAll(set, elements);
        return set;
    }

    /**
     * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given comparator.
     *
     * <p>
     * <b>Note:</b> if mutability is not required, use {@code
     * ImmutableSortedSet.orderedBy(comparator).build()} instead.
     *
     * <p>
     * <b>Note for Java 7 and later:</b> this method is now unnecessary and should be treated as
     * deprecated. Instead, use the {@code TreeSet} constructor directly, taking advantage of the
     * new <a href="http://goo.gl/iz2Wi">"diamond" syntax</a>. One caveat to this is that the {@code
     * TreeSet} constructor uses a null {@code Comparator} to mean "natural ordering," whereas this
     * factory rejects null. Clean your code accordingly.
     *
     * @param comparator the comparator to use to sort the set
     * @return a new, empty {@code TreeSet}
     * @throws NullPointerException if {@code comparator} is null
     */
    public static <E> TreeSet<E> newTreeSet(Comparator<? super E> comparator) {
        return new TreeSet<E>(checkNotNull(comparator));
    }

    /**
     * Creates an empty {@code Set} that uses identity to determine equality. It compares object
     * references, instead of calling {@code equals}, to determine whether a provided object matches
     * an element in the set. For example, {@code contains} returns {@code false} when passed an
     * object that equals a set member, but isn't the same instance. This behavior is similar to the
     * way {@code IdentityHashMap} handles key lookups.
     *
     * @since 8.0
     */
    public static <E> Set<E> newIdentityHashSet() {
        return Collections.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap());
    }

    /**
     * Creates an empty {@code CopyOnWriteArraySet} instance.
     *
     * <p>
     * <b>Note:</b> if you need an immutable empty {@link Set}, use {@link Collections#emptySet}
     * instead.
     *
     * @return a new, empty {@code CopyOnWriteArraySet}
     * @since 12.0
     */
    @GwtIncompatible // CopyOnWriteArraySet
    public static <E> CopyOnWriteArraySet<E> newCopyOnWriteArraySet() {
        return new CopyOnWriteArraySet<E>();
    }

    /**
     * Creates a {@code CopyOnWriteArraySet} instance containing the given elements.
     *
     * @param elements the elements that the set should contain, in order
     * @return a new {@code CopyOnWriteArraySet} containing those elements
     * @since 12.0
     */
    @GwtIncompatible // CopyOnWriteArraySet
    public static <E> CopyOnWriteArraySet<E> newCopyOnWriteArraySet(Iterable<? extends E> elements) {
        // We copy elements to an ArrayList first, rather than incurring the
        // quadratic cost of adding them to the COWAS directly.
        Collection<? extends E> elementsCollection =
                (elements instanceof Collection) ? Collections2.cast(elements) : Lists.newArrayList(elements);
        return new CopyOnWriteArraySet<E>(elementsCollection);
    }

    /**
     * Creates an {@code EnumSet} consisting of all enum values that are not in the specified
     * collection. If the collection is an {@link EnumSet}, this method has the same behavior as
     * {@link EnumSet#complementOf}. Otherwise, the specified collection must contain at least one
     * element, in order to determine the element type. If the collection could be empty, use
     * {@link #complementOf(Collection, Class)} instead of this method.
     *
     * @param collection the collection whose complement should be stored in the enum set
     * @return a new, modifiable {@code EnumSet} containing all values of the enum that aren't
     *         present in the given collection
     * @throws IllegalArgumentException if {@code collection} is not an {@code EnumSet} instance and
     *         contains no elements
     */
    public static <E extends Enum<E>> EnumSet<E> complementOf(Collection<E> collection) {
        if (collection instanceof EnumSet) {
            return EnumSet.complementOf((EnumSet<E>) collection);
        }
        checkArgument(!collection.isEmpty(), "collection is empty; use the other version of this method");
        Class<E> type = collection.iterator().next().getDeclaringClass();
        return makeComplementByHand(collection, type);
    }

    /**
     * Creates an {@code EnumSet} consisting of all enum values that are not in the specified
     * collection. This is equivalent to {@link EnumSet#complementOf}, but can act on any input
     * collection, as long as the elements are of enum type.
     *
     * @param collection the collection whose complement should be stored in the {@code EnumSet}
     * @param type the type of the elements in the set
     * @return a new, modifiable {@code EnumSet} initially containing all the values of the enum not
     *         present in the given collection
     */
    public static <E extends Enum<E>> EnumSet<E> complementOf(Collection<E> collection, Class<E> type) {
        checkNotNull(collection);
        return (collection instanceof EnumSet) ? EnumSet.complementOf((EnumSet<E>) collection)
                : makeComplementByHand(collection, type);
    }

    private static <E extends Enum<E>> EnumSet<E> makeComplementByHand(Collection<E> collection, Class<E> type) {
        EnumSet<E> result = EnumSet.allOf(type);
        result.removeAll(collection);
        return result;
    }

    /**
     * Returns a set backed by the specified map. The resulting set displays the same ordering,
     * concurrency, and performance characteristics as the backing map. In essence, this factory
     * method provides a {@link Set} implementation corresponding to any {@link Map} implementation.
     * There is no need to use this method on a {@link Map} implementation that already has a
     * corresponding {@link Set} implementation (such as {@link java.util.HashMap} or
     * {@link java.util.TreeMap}).
     *
     * <p>
     * Each method invocation on the set returned by this method results in exactly one method
     * invocation on the backing map or its {@code keySet} view, with one exception. The
     * {@code addAll} method is implemented as a sequence of {@code put} invocations on the backing
     * map.
     *
     * <p>
     * The specified map must be empty at the time this method is invoked, and should not be
     * accessed directly after this method returns. These conditions are ensured if the map is
     * created empty, passed directly to this method, and no reference to the map is retained, as
     * illustrated in the following code fragment:
     * 
     * <pre>
     * {
     *     &#64;code
     *
     *     Set<Object> identityHashSet = Sets.newSetFromMap(new IdentityHashMap<Object, Boolean>());
     * }
     * </pre>
     *
     * <p>
     * The returned set is serializable if the backing map is.
     *
     * @param map the backing map
     * @return the set backed by the map
     * @throws IllegalArgumentException if {@code map} is not empty
     * @deprecated Use {@link Collections#newSetFromMap} instead. This method will be removed in
     *             December 2017.
     */
    @Deprecated
    public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
        return Collections.newSetFromMap(map);
    }

    /**
     * An unmodifiable view of a set which may be backed by other sets; this view will change as the
     * backing sets do. Contains methods to copy the data into a new set which will then remain
     * stable. There is usually no reason to retain a reference of type {@code SetView}; typically,
     * you either use it as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or
     * {@link #copyInto} and forget the {@code SetView} itself.
     *
     * @since 2.0
     */
    public abstract static class SetView<E> extends AbstractSet<E> {
        private SetView() {} // no subclasses but our own

        /**
         * Returns an immutable copy of the current contents of this set view. Does not support null
         * elements.
         *
         * <p>
         * <b>Warning:</b> this may have unexpected results if a backing set of this view uses a
         * nonstandard notion of equivalence, for example if it is a {@link TreeSet} using a
         * comparator that is inconsistent with {@link Object#equals(Object)}.
         */
        public ImmutableSet<E> immutableCopy() {
            return ImmutableSet.copyOf(this);
        }

        /**
         * Copies the current contents of this set view into an existing set. This method has
         * equivalent behavior to {@code set.addAll(this)}, assuming that all the sets involved are
         * based on the same notion of equivalence.
         *
         * @return a reference to {@code set}, for convenience
         */
        // Note: S should logically extend Set<? super E> but can't due to either
        // some javac bug or some weirdness in the spec, not sure which.
        @CanIgnoreReturnValue
        public <S extends Set<E>> S copyInto(S set) {
            set.addAll(this);
            return set;
        }

        /**
         * Guaranteed to throw an exception and leave the collection unmodified.
         *
         * @throws UnsupportedOperationException always
         * @deprecated Unsupported operation.
         */
        @CanIgnoreReturnValue
        @Deprecated
        @Override
        public final boolean add(E e) {
            throw new UnsupportedOperationException();
        }

        /**
         * Guaranteed to throw an exception and leave the collection unmodified.
         *
         * @throws UnsupportedOperationException always
         * @deprecated Unsupported operation.
         */
        @CanIgnoreReturnValue
        @Deprecated
        @Override
        public final boolean remove(Object object) {
            throw new UnsupportedOperationException();
        }

        /**
         * Guaranteed to throw an exception and leave the collection unmodified.
         *
         * @throws UnsupportedOperationException always
         * @deprecated Unsupported operation.
         */
        @CanIgnoreReturnValue
        @Deprecated
        @Override
        public final boolean addAll(Collection<? extends E> newElements) {
            throw new UnsupportedOperationException();
        }

        /**
         * Guaranteed to throw an exception and leave the collection unmodified.
         *
         * @throws UnsupportedOperationException always
         * @deprecated Unsupported operation.
         */
        @CanIgnoreReturnValue
        @Deprecated
        @Override
        public final boolean removeAll(Collection<?> oldElements) {
            throw new UnsupportedOperationException();
        }

        /**
         * Guaranteed to throw an exception and leave the collection unmodified.
         *
         * @throws UnsupportedOperationException always
         * @deprecated Unsupported operation.
         */
        @CanIgnoreReturnValue
        @Deprecated
        @Override
        public final boolean removeIf(java.util.function.Predicate<? super E> filter) {
            throw new UnsupportedOperationException();
        }

        /**
         * Guaranteed to throw an exception and leave the collection unmodified.
         *
         * @throws UnsupportedOperationException always
         * @deprecated Unsupported operation.
         */
        @CanIgnoreReturnValue
        @Deprecated
        @Override
        public final boolean retainAll(Collection<?> elementsToKeep) {
            throw new UnsupportedOperationException();
        }

        /**
         * Guaranteed to throw an exception and leave the collection unmodified.
         *
         * @throws UnsupportedOperationException always
         * @deprecated Unsupported operation.
         */
        @Deprecated
        @Override
        public final void clear() {
            throw new UnsupportedOperationException();
        }

        /**
         * Scope the return type to {@link UnmodifiableIterator} to ensure this is an unmodifiable
         * view.
         *
         * @since 20.0 (present with return type {@link Iterator} since 2.0)
         */
        @Override
        public abstract UnmodifiableIterator<E> iterator();
    }

    /**
     * Returns an unmodifiable <b>view</b> of the union of two sets. The returned set contains all
     * elements that are contained in either backing set. Iterating over the returned set iterates
     * first over all the elements of {@code set1}, then over each element of {@code set2}, in
     * order, that is not contained in {@code set1}.
     *
     * <p>
     * Results are undefined if {@code set1} and {@code set2} are sets based on different
     * equivalence relations (as {@link HashSet}, {@link TreeSet}, and the {@link Map#keySet} of an
     * {@code IdentityHashMap} all are).
     */
    public static <E> SetView<E> union(final Set<? extends E> set1, final Set<? extends E> set2) {
        checkNotNull(set1, "set1");
        checkNotNull(set2, "set2");

        final Set<? extends E> set2minus1 = difference(set2, set1);

        return new SetView<E>() {
            @Override
            public int size() {
                return IntMath.saturatedAdd(set1.size(), set2minus1.size());
            }

            @Override
            public boolean isEmpty() {
                return set1.isEmpty() && set2.isEmpty();
            }

            @Override
            public UnmodifiableIterator<E> iterator() {
                return Iterators.unmodifiableIterator(Iterators.concat(set1.iterator(), set2minus1.iterator()));
            }

            @Override
            public Stream<E> stream() {
                return Stream.concat(set1.stream(), set2minus1.stream());
            }

            @Override
            public Stream<E> parallelStream() {
                return Stream.concat(set1.parallelStream(), set2minus1.parallelStream());
            }

            @Override
            public boolean contains(Object object) {
                return set1.contains(object) || set2.contains(object);
            }

            @Override
            public <S extends Set<E>> S copyInto(S set) {
                set.addAll(set1);
                set.addAll(set2);
                return set;
            }

            @Override
            public ImmutableSet<E> immutableCopy() {
                return new ImmutableSet.Builder<E>().addAll(set1).addAll(set2).build();
            }
        };
    }

    /**
     * Returns an unmodifiable <b>view</b> of the intersection of two sets. The returned set
     * contains all elements that are contained by both backing sets. The iteration order of the
     * returned set matches that of {@code set1}.
     *
     * <p>
     * Results are undefined if {@code set1} and {@code set2} are sets based on different
     * equivalence relations (as {@code HashSet}, {@code TreeSet}, and the keySet of an
     * {@code IdentityHashMap} all are).
     *
     * <p>
     * <b>Note:</b> The returned view performs slightly better when {@code
     * set1} is the smaller of the two sets. If you have reason to believe one of your sets will
     * generally be smaller than the other, pass it first. Unfortunately, since this method sets the
     * generic type of the returned set based on the type of the first set passed, this could in
     * rare cases force you to make a cast, for example:
     * 
     * <pre>
     *    {@code
     *
     *   Set<Object> aFewBadObjects = ...
     *   Set<String> manyBadStrings = ...
     *
     *   // impossible for a non-String to be in the intersection
     *   SuppressWarnings("unchecked")
     *   Set<String> badStrings = (Set) Sets.intersection(
     *       aFewBadObjects, manyBadStrings);}
     * </pre>
     *
     * <p>
     * This is unfortunate, but should come up only very rarely.
     */
    public static <E> SetView<E> intersection(final Set<E> set1, final Set<?> set2) {
        checkNotNull(set1, "set1");
        checkNotNull(set2, "set2");

        final Predicate<Object> inSet2 = Predicates.in(set2);
        return new SetView<E>() {
            @Override
            public UnmodifiableIterator<E> iterator() {
                return Iterators.filter(set1.iterator(), inSet2);
            }

            @Override
            public Stream<E> stream() {
                return set1.stream().filter(inSet2);
            }

            @Override
            public Stream<E> parallelStream() {
                return set1.parallelStream().filter(inSet2);
            }

            @Override
            public int size() {
                return Iterators.size(iterator());
            }

            @Override
            public boolean isEmpty() {
                return !iterator().hasNext();
            }

            @Override
            public boolean contains(Object object) {
                return set1.contains(object) && set2.contains(object);
            }

            @Override
            public boolean containsAll(Collection<?> collection) {
                return set1.containsAll(collection) && set2.containsAll(collection);
            }
        };
    }

    /**
     * Returns an unmodifiable <b>view</b> of the difference of two sets. The returned set contains
     * all elements that are contained by {@code set1} and not contained by {@code set2}.
     * {@code set2} may also contain elements not present in {@code set1}; these are simply ignored.
     * The iteration order of the returned set matches that of {@code set1}.
     *
     * <p>
     * Results are undefined if {@code set1} and {@code set2} are sets based on different
     * equivalence relations (as {@code HashSet}, {@code TreeSet}, and the keySet of an
     * {@code IdentityHashMap} all are).
     */
    public static <E> SetView<E> difference(final Set<E> set1, final Set<?> set2) {
        checkNotNull(set1, "set1");
        checkNotNull(set2, "set2");

        final Predicate<Object> notInSet2 = Predicates.not(Predicates.in(set2));
        return new SetView<E>() {
            @Override
            public UnmodifiableIterator<E> iterator() {
                return Iterators.filter(set1.iterator(), notInSet2);
            }

            @Override
            public Stream<E> stream() {
                return set1.stream().filter(notInSet2);
            }

            @Override
            public Stream<E> parallelStream() {
                return set1.parallelStream().filter(notInSet2);
            }

            @Override
            public int size() {
                return Iterators.size(iterator());
            }

            @Override
            public boolean isEmpty() {
                return set2.containsAll(set1);
            }

            @Override
            public boolean contains(Object element) {
                return set1.contains(element) && !set2.contains(element);
            }
        };
    }

    /**
     * Returns an unmodifiable <b>view</b> of the symmetric difference of two sets. The returned set
     * contains all elements that are contained in either {@code set1} or {@code set2} but not in
     * both. The iteration order of the returned set is undefined.
     *
     * <p>
     * Results are undefined if {@code set1} and {@code set2} are sets based on different
     * equivalence relations (as {@code HashSet}, {@code TreeSet}, and the keySet of an
     * {@code IdentityHashMap} all are).
     *
     * @since 3.0
     */
    public static <E> SetView<E> symmetricDifference(final Set<? extends E> set1, final Set<? extends E> set2) {
        checkNotNull(set1, "set1");
        checkNotNull(set2, "set2");

        return new SetView<E>() {
            @Override
            public UnmodifiableIterator<E> iterator() {
                final Iterator<? extends E> itr1 = set1.iterator();
                final Iterator<? extends E> itr2 = set2.iterator();
                return new AbstractIterator<E>() {
                    @Override
                    public E computeNext() {
                        while (itr1.hasNext()) {
                            E elem1 = itr1.next();
                            if (!set2.contains(elem1)) {
                                return elem1;
                            }
                        }
                        while (itr2.hasNext()) {
                            E elem2 = itr2.next();
                            if (!set1.contains(elem2)) {
                                return elem2;
                            }
                        }
                        return endOfData();
                    }
                };
            }

            @Override
            public int size() {
                return Iterators.size(iterator());
            }

            @Override
            public boolean isEmpty() {
                return set1.equals(set2);
            }

            @Override
            public boolean contains(Object element) {
                return set1.contains(element) ^ set2.contains(element);
            }
        };
    }

    /**
     * Returns the elements of {@code unfiltered} that satisfy a predicate. The returned set is a
     * live view of {@code unfiltered}; changes to one affect the other.
     *
     * <p>
     * The resulting set's iterator does not support {@code remove()}, but all other set methods are
     * supported. When given an element that doesn't satisfy the predicate, the set's {@code add()}
     * and {@code addAll()} methods throw an {@link IllegalArgumentException}. When methods such as
     * {@code
     * removeAll()} and {@code clear()} are called on the filtered set, only elements that satisfy
     * the filter will be removed from the underlying set.
     *
     * <p>
     * The returned set isn't threadsafe or serializable, even if {@code unfiltered} is.
     *
     * <p>
     * Many of the filtered set's methods, such as {@code size()}, iterate across every element in
     * the underlying set and determine which elements satisfy the filter. When a live view is
     * <i>not</i> needed, it may be faster to copy {@code Iterables.filter(unfiltered, predicate)}
     * and use the copy.
     *
     * <p>
     * <b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at
     * {@link Predicate#apply}. Do not provide a predicate such as
     * {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See
     * {@link Iterables#filter(Iterable, Class)} for related functionality.)
     *
     * <p>
     * <b>Java 8 users:</b> many use cases for this method are better addressed by
     * {@link java.util.stream.Stream#filter}. This method is not being deprecated, but we gently
     * encourage you to migrate to streams.
     */
    // TODO(kevinb): how to omit that last sentence when building GWT javadoc?
    public static <E> Set<E> filter(Set<E> unfiltered, Predicate<? super E> predicate) {
        if (unfiltered instanceof SortedSet) {
            return filter((SortedSet<E>) unfiltered, predicate);
        }
        if (unfiltered instanceof FilteredSet) {
            // Support clear(), removeAll(), and retainAll() when filtering a filtered
            // collection.
            FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
            Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate);
            return new FilteredSet<E>((Set<E>) filtered.unfiltered, combinedPredicate);
        }

        return new FilteredSet<E>(checkNotNull(unfiltered), checkNotNull(predicate));
    }

    private static class FilteredSet<E> extends FilteredCollection<E> implements Set<E> {
        FilteredSet(Set<E> unfiltered, Predicate<? super E> predicate) {
            super(unfiltered, predicate);
        }

        @Override
        public boolean equals(@Nullable Object object) {
            return equalsImpl(this, object);
        }

        @Override
        public int hashCode() {
            return hashCodeImpl(this);
        }
    }

    /**
     * Returns the elements of a {@code SortedSet}, {@code unfiltered}, that satisfy a predicate.
     * The returned set is a live view of {@code unfiltered}; changes to one affect the other.
     *
     * <p>
     * The resulting set's iterator does not support {@code remove()}, but all other set methods are
     * supported. When given an element that doesn't satisfy the predicate, the set's {@code add()}
     * and {@code addAll()} methods throw an {@link IllegalArgumentException}. When methods such as
     * {@code removeAll()} and {@code clear()} are called on the filtered set, only elements that
     * satisfy the filter will be removed from the underlying set.
     *
     * <p>
     * The returned set isn't threadsafe or serializable, even if {@code unfiltered} is.
     *
     * <p>
     * Many of the filtered set's methods, such as {@code size()}, iterate across every element in
     * the underlying set and determine which elements satisfy the filter. When a live view is
     * <i>not</i> needed, it may be faster to copy {@code Iterables.filter(unfiltered, predicate)}
     * and use the copy.
     *
     * <p>
     * <b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at
     * {@link Predicate#apply}. Do not provide a predicate such as
     * {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See
     * {@link Iterables#filter(Iterable, Class)} for related functionality.)
     *
     * @since 11.0
     */
    public static <E> SortedSet<E> filter(SortedSet<E> unfiltered, Predicate<? super E> predicate) {
        if (unfiltered instanceof FilteredSet) {
            // Support clear(), removeAll(), and retainAll() when filtering a filtered
            // collection.
            FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
            Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate);
            return new FilteredSortedSet<E>((SortedSet<E>) filtered.unfiltered, combinedPredicate);
        }

        return new FilteredSortedSet<E>(checkNotNull(unfiltered), checkNotNull(predicate));
    }

    private static class FilteredSortedSet<E> extends FilteredSet<E> implements SortedSet<E> {

        FilteredSortedSet(SortedSet<E> unfiltered, Predicate<? super E> predicate) {
            super(unfiltered, predicate);
        }

        @Override
        public Comparator<? super E> comparator() {
            return ((SortedSet<E>) unfiltered).comparator();
        }

        @Override
        public SortedSet<E> subSet(E fromElement, E toElement) {
            return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).subSet(fromElement, toElement), predicate);
        }

        @Override
        public SortedSet<E> headSet(E toElement) {
            return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).headSet(toElement), predicate);
        }

        @Override
        public SortedSet<E> tailSet(E fromElement) {
            return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).tailSet(fromElement), predicate);
        }

        @Override
        public E first() {
            return iterator().next();
        }

        @Override
        public E last() {
            SortedSet<E> sortedUnfiltered = (SortedSet<E>) unfiltered;
            while (true) {
                E element = sortedUnfiltered.last();
                if (predicate.apply(element)) {
                    return element;
                }
                sortedUnfiltered = sortedUnfiltered.headSet(element);
            }
        }
    }

    /**
     * Returns the elements of a {@code NavigableSet}, {@code unfiltered}, that satisfy a predicate.
     * The returned set is a live view of {@code unfiltered}; changes to one affect the other.
     *
     * <p>
     * The resulting set's iterator does not support {@code remove()}, but all other set methods are
     * supported. When given an element that doesn't satisfy the predicate, the set's {@code add()}
     * and {@code addAll()} methods throw an {@link IllegalArgumentException}. When methods such as
     * {@code removeAll()} and {@code clear()} are called on the filtered set, only elements that
     * satisfy the filter will be removed from the underlying set.
     *
     * <p>
     * The returned set isn't threadsafe or serializable, even if {@code unfiltered} is.
     *
     * <p>
     * Many of the filtered set's methods, such as {@code size()}, iterate across every element in
     * the underlying set and determine which elements satisfy the filter. When a live view is
     * <i>not</i> needed, it may be faster to copy {@code Iterables.filter(unfiltered, predicate)}
     * and use the copy.
     *
     * <p>
     * <b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at
     * {@link Predicate#apply}. Do not provide a predicate such as
     * {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See
     * {@link Iterables#filter(Iterable, Class)} for related functionality.)
     *
     * @since 14.0
     */
    @GwtIncompatible // NavigableSet
    @SuppressWarnings("unchecked")
    public static <E> NavigableSet<E> filter(NavigableSet<E> unfiltered, Predicate<? super E> predicate) {
        if (unfiltered instanceof FilteredSet) {
            // Support clear(), removeAll(), and retainAll() when filtering a filtered
            // collection.
            FilteredSet<E> filtered = (FilteredSet<E>) unfiltered;
            Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate);
            return new FilteredNavigableSet<E>((NavigableSet<E>) filtered.unfiltered, combinedPredicate);
        }

        return new FilteredNavigableSet<E>(checkNotNull(unfiltered), checkNotNull(predicate));
    }

    @GwtIncompatible // NavigableSet
    private static class FilteredNavigableSet<E> extends FilteredSortedSet<E> implements NavigableSet<E> {
        FilteredNavigableSet(NavigableSet<E> unfiltered, Predicate<? super E> predicate) {
            super(unfiltered, predicate);
        }

        NavigableSet<E> unfiltered() {
            return (NavigableSet<E>) unfiltered;
        }

        @Override
        @Nullable
        public E lower(E e) {
            return Iterators.getNext(headSet(e, false).descendingIterator(), null);
        }

        @Override
        @Nullable
        public E floor(E e) {
            return Iterators.getNext(headSet(e, true).descendingIterator(), null);
        }

        @Override
        public E ceiling(E e) {
            return Iterables.getFirst(tailSet(e, true), null);
        }

        @Override
        public E higher(E e) {
            return Iterables.getFirst(tailSet(e, false), null);
        }

        @Override
        public E pollFirst() {
            return Iterables.removeFirstMatching(unfiltered(), predicate);
        }

        @Override
        public E pollLast() {
            return Iterables.removeFirstMatching(unfiltered().descendingSet(), predicate);
        }

        @Override
        public NavigableSet<E> descendingSet() {
            return Sets.filter(unfiltered().descendingSet(), predicate);
        }

        @Override
        public Iterator<E> descendingIterator() {
            return Iterators.filter(unfiltered().descendingIterator(), predicate);
        }

        @Override
        public E last() {
            return descendingIterator().next();
        }

        @Override
        public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
            return filter(unfiltered().subSet(fromElement, fromInclusive, toElement, toInclusive), predicate);
        }

        @Override
        public NavigableSet<E> headSet(E toElement, boolean inclusive) {
            return filter(unfiltered().headSet(toElement, inclusive), predicate);
        }

        @Override
        public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
            return filter(unfiltered().tailSet(fromElement, inclusive), predicate);
        }
    }

    /**
     * Returns every possible list that can be formed by choosing one element from each of the given
     * sets in order; the "n-ary <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
     * product</a>" of the sets. For example:
     * 
     * <pre>
     *    {@code
     *
     *   Sets.cartesianProduct(ImmutableList.of(
     *       ImmutableSet.of(1, 2),
     *       ImmutableSet.of("A", "B", "C")))}
     * </pre>
     *
     * <p>
     * returns a set containing six lists:
     *
     * <ul>
     * <li>{@code ImmutableList.of(1, "A")}
     * <li>{@code ImmutableList.of(1, "B")}
     * <li>{@code ImmutableList.of(1, "C")}
     * <li>{@code ImmutableList.of(2, "A")}
     * <li>{@code ImmutableList.of(2, "B")}
     * <li>{@code ImmutableList.of(2, "C")}
     * </ul>
     *
     * <p>
     * The result is guaranteed to be in the "traditional", lexicographical order for Cartesian
     * products that you would get from nesting for loops:
     * 
     * <pre>
     *    {@code
     *
     *   for (B b0 : sets.get(0)) {
     *     for (B b1 : sets.get(1)) {
     *       ...
     *       ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
     *       // operate on tuple
     *     }
     *   }}
     * </pre>
     *
     * <p>
     * Note that if any input set is empty, the Cartesian product will also be empty. If no sets at
     * all are provided (an empty list), the resulting Cartesian product has one element, an empty
     * list (counter-intuitive, but mathematically consistent).
     *
     * <p>
     * <i>Performance notes:</i> while the cartesian product of sets of size {@code m, n, p} is a
     * set of size {@code m x n x p}, its actual memory consumption is much smaller. When the
     * cartesian set is constructed, the input sets are merely copied. Only as the resulting set is
     * iterated are the individual lists created, and these are not retained after iteration.
     *
     * @param sets the sets to choose elements from, in the order that the elements chosen from
     *        those sets should appear in the resulting lists
     * @param <B> any common base class shared by all axes (often just {@link Object})
     * @return the Cartesian product, as an immutable set containing immutable lists
     * @throws NullPointerException if {@code sets}, any one of the {@code sets}, or any element of
     *         a provided set is null
     * @since 2.0
     */
    public static <B> Set<List<B>> cartesianProduct(List<? extends Set<? extends B>> sets) {
        return CartesianSet.create(sets);
    }

    /**
     * Returns every possible list that can be formed by choosing one element from each of the given
     * sets in order; the "n-ary <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
     * product</a>" of the sets. For example:
     * 
     * <pre>
     *    {@code
     *
     *   Sets.cartesianProduct(
     *       ImmutableSet.of(1, 2),
     *       ImmutableSet.of("A", "B", "C"))}
     * </pre>
     *
     * <p>
     * returns a set containing six lists:
     *
     * <ul>
     * <li>{@code ImmutableList.of(1, "A")}
     * <li>{@code ImmutableList.of(1, "B")}
     * <li>{@code ImmutableList.of(1, "C")}
     * <li>{@code ImmutableList.of(2, "A")}
     * <li>{@code ImmutableList.of(2, "B")}
     * <li>{@code ImmutableList.of(2, "C")}
     * </ul>
     *
     * <p>
     * The result is guaranteed to be in the "traditional", lexicographical order for Cartesian
     * products that you would get from nesting for loops:
     * 
     * <pre>
     *    {@code
     *
     *   for (B b0 : sets.get(0)) {
     *     for (B b1 : sets.get(1)) {
     *       ...
     *       ImmutableList<B> tuple = ImmutableList.of(b0, b1, ...);
     *       // operate on tuple
     *     }
     *   }}
     * </pre>
     *
     * <p>
     * Note that if any input set is empty, the Cartesian product will also be empty. If no sets at
     * all are provided (an empty list), the resulting Cartesian product has one element, an empty
     * list (counter-intuitive, but mathematically consistent).
     *
     * <p>
     * <i>Performance notes:</i> while the cartesian product of sets of size {@code m, n, p} is a
     * set of size {@code m x n x p}, its actual memory consumption is much smaller. When the
     * cartesian set is constructed, the input sets are merely copied. Only as the resulting set is
     * iterated are the individual lists created, and these are not retained after iteration.
     *
     * @param sets the sets to choose elements from, in the order that the elements chosen from
     *        those sets should appear in the resulting lists
     * @param <B> any common base class shared by all axes (often just {@link Object})
     * @return the Cartesian product, as an immutable set containing immutable lists
     * @throws NullPointerException if {@code sets}, any one of the {@code sets}, or any element of
     *         a provided set is null
     * @since 2.0
     */
    public static <B> Set<List<B>> cartesianProduct(Set<? extends B>... sets) {
        return cartesianProduct(Arrays.asList(sets));
    }

    private static final class CartesianSet<E> extends ForwardingCollection<List<E>> implements Set<List<E>> {
        private final transient ImmutableList<ImmutableSet<E>> axes;
        private final transient CartesianList<E> delegate;

        static <E> Set<List<E>> create(List<? extends Set<? extends E>> sets) {
            ImmutableList.Builder<ImmutableSet<E>> axesBuilder =
                    new ImmutableList.Builder<ImmutableSet<E>>(sets.size());
            for (Set<? extends E> set : sets) {
                ImmutableSet<E> copy = ImmutableSet.copyOf(set);
                if (copy.isEmpty()) {
                    return ImmutableSet.of();
                }
                axesBuilder.add(copy);
            }
            final ImmutableList<ImmutableSet<E>> axes = axesBuilder.build();
            ImmutableList<List<E>> listAxes = new ImmutableList<List<E>>() {
                @Override
                public int size() {
                    return axes.size();
                }

                @Override
                public List<E> get(int index) {
                    return axes.get(index).asList();
                }

                @Override
                boolean isPartialView() {
                    return true;
                }
            };
            return new CartesianSet<E>(axes, new CartesianList<E>(listAxes));
        }

        private CartesianSet(ImmutableList<ImmutableSet<E>> axes, CartesianList<E> delegate) {
            this.axes = axes;
            this.delegate = delegate;
        }

        @Override
        protected Collection<List<E>> delegate() {
            return delegate;
        }

        @Override
        public boolean equals(@Nullable Object object) {
            // Warning: this is broken if size() == 0, so it is critical that we
            // substitute an empty ImmutableSet to the user in place of this
            if (object instanceof CartesianSet) {
                CartesianSet<?> that = (CartesianSet<?>) object;
                return this.axes.equals(that.axes);
            }
            return super.equals(object);
        }

        @Override
        public int hashCode() {
            // Warning: this is broken if size() == 0, so it is critical that we
            // substitute an empty ImmutableSet to the user in place of this

            // It's a weird formula, but tests prove it works.
            int adjust = size() - 1;
            for (int i = 0; i < axes.size(); i++) {
                adjust *= 31;
                adjust = ~~adjust;
                // in GWT, we have to deal with integer overflow carefully
            }
            int hash = 1;
            for (Set<E> axis : axes) {
                hash = 31 * hash + (size() / axis.size() * axis.hashCode());

                hash = ~~hash;
            }
            hash += adjust;
            return ~~hash;
        }
    }

    /**
     * Returns the set of all possible subsets of {@code set}. For example,
     * {@code powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{}, {1}, {2}, {1, 2}}}.
     *
     * <p>
     * Elements appear in these subsets in the same iteration order as they appeared in the input
     * set. The order in which these subsets appear in the outer set is undefined. Note that the
     * power set of the empty set is not the empty set, but a one-element set containing the empty
     * set.
     *
     * <p>
     * The returned set and its constituent sets use {@code equals} to decide whether two elements
     * are identical, even if the input set uses a different concept of equivalence.
     *
     * <p>
     * <i>Performance notes:</i> while the power set of a set with size {@code
     * n} is of size {@code 2^n}, its memory usage is only {@code O(n)}. When the power set is
     * constructed, the input set is merely copied. Only as the power set is iterated are the
     * individual subsets created, and these subsets themselves occupy only a small constant amount
     * of memory.
     *
     * @param set the set of elements to construct a power set from
     * @return the power set, as an immutable set of immutable sets
     * @throws IllegalArgumentException if {@code set} has more than 30 unique elements (causing the
     *         power set size to exceed the {@code int} range)
     * @throws NullPointerException if {@code set} is or contains {@code null}
     * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at Wikipedia</a>
     * @since 4.0
     */
    @GwtCompatible(serializable = false)
    public static <E> Set<Set<E>> powerSet(Set<E> set) {
        return new PowerSet<E>(set);
    }

    private static final class SubSet<E> extends AbstractSet<E> {
        private final ImmutableMap<E, Integer> inputSet;
        private final int mask;

        SubSet(ImmutableMap<E, Integer> inputSet, int mask) {
            this.inputSet = inputSet;
            this.mask = mask;
        }

        @Override
        public Iterator<E> iterator() {
            return new UnmodifiableIterator<E>() {
                final ImmutableList<E> elements = inputSet.keySet().asList();
                int remainingSetBits = mask;

                @Override
                public boolean hasNext() {
                    return remainingSetBits != 0;
                }

                @Override
                public E next() {
                    int index = Integer.numberOfTrailingZeros(remainingSetBits);
                    if (index == 32) {
                        throw new NoSuchElementException();
                    }
                    remainingSetBits &= ~(1 << index);
                    return elements.get(index);
                }
            };
        }

        @Override
        public int size() {
            return Integer.bitCount(mask);
        }

        @Override
        public boolean contains(@Nullable Object o) {
            Integer index = inputSet.get(o);
            return index != null && (mask & (1 << index)) != 0;
        }
    }

    private static final class PowerSet<E> extends AbstractSet<Set<E>> {
        final ImmutableMap<E, Integer> inputSet;

        PowerSet(Set<E> input) {
            this.inputSet = Maps.indexMap(input);
            checkArgument(inputSet.size() <= 30, "Too many elements to create power set: %s > 30", inputSet.size());
        }

        @Override
        public int size() {
            return 1 << inputSet.size();
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        @Override
        public Iterator<Set<E>> iterator() {
            return new AbstractIndexedListIterator<Set<E>>(size()) {
                @Override
                protected Set<E> get(final int setBits) {
                    return new SubSet<E>(inputSet, setBits);
                }
            };
        }

        @Override
        public boolean contains(@Nullable Object obj) {
            if (obj instanceof Set) {
                Set<?> set = (Set<?>) obj;
                return inputSet.keySet().containsAll(set);
            }
            return false;
        }

        @Override
        public boolean equals(@Nullable Object obj) {
            if (obj instanceof PowerSet) {
                PowerSet<?> that = (PowerSet<?>) obj;
                return inputSet.equals(that.inputSet);
            }
            return super.equals(obj);
        }

        @Override
        public int hashCode() {
            /*
             * The sum of the sums of the hash codes in each subset is just the sum of each input
             * element's hash code times the number of sets that element appears in. Each element
             * appears in exactly half of the 2^n sets, so:
             */
            return inputSet.keySet().hashCode() << (inputSet.size() - 1);
        }

        @Override
        public String toString() {
            return "powerSet(" + inputSet + ")";
        }
    }

    /**
     * An implementation for {@link Set#hashCode()}.
     */
    static int hashCodeImpl(Set<?> s) {
        int hashCode = 0;
        for (Object o : s) {
            hashCode += o != null ? o.hashCode() : 0;

            hashCode = ~~hashCode;
            // Needed to deal with unusual integer overflow in GWT.
        }
        return hashCode;
    }

    /**
     * An implementation for {@link Set#equals(Object)}.
     */
    static boolean equalsImpl(Set<?> s, @Nullable Object object) {
        if (s == object) {
            return true;
        }
        if (object instanceof Set) {
            Set<?> o = (Set<?>) object;

            try {
                return s.size() == o.size() && s.containsAll(o);
            } catch (NullPointerException ignored) {
                return false;
            } catch (ClassCastException ignored) {
                return false;
            }
        }
        return false;
    }

    /**
     * Returns an unmodifiable view of the specified navigable set. This method allows modules to
     * provide users with "read-only" access to internal navigable sets. Query operations on the
     * returned set "read through" to the specified set, and attempts to modify the returned set,
     * whether direct or via its collection views, result in an
     * {@code UnsupportedOperationException}.
     *
     * <p>
     * The returned navigable set will be serializable if the specified navigable set is
     * serializable.
     *
     * @param set the navigable set for which an unmodifiable view is to be returned
     * @return an unmodifiable view of the specified navigable set
     * @since 12.0
     */
    public static <E> NavigableSet<E> unmodifiableNavigableSet(NavigableSet<E> set) {
        if (set instanceof ImmutableSortedSet || set instanceof UnmodifiableNavigableSet) {
            return set;
        }
        return new UnmodifiableNavigableSet<E>(set);
    }

    static final class UnmodifiableNavigableSet<E> extends ForwardingSortedSet<E>
            implements NavigableSet<E>, Serializable {
        private final NavigableSet<E> delegate;

        UnmodifiableNavigableSet(NavigableSet<E> delegate) {
            this.delegate = checkNotNull(delegate);
        }

        @Override
        protected SortedSet<E> delegate() {
            return Collections.unmodifiableSortedSet(delegate);
        }

        @Override
        public E lower(E e) {
            return delegate.lower(e);
        }

        @Override
        public E floor(E e) {
            return delegate.floor(e);
        }

        @Override
        public E ceiling(E e) {
            return delegate.ceiling(e);
        }

        @Override
        public E higher(E e) {
            return delegate.higher(e);
        }

        @Override
        public E pollFirst() {
            throw new UnsupportedOperationException();
        }

        @Override
        public E pollLast() {
            throw new UnsupportedOperationException();
        }

        private transient UnmodifiableNavigableSet<E> descendingSet;

        @Override
        public NavigableSet<E> descendingSet() {
            UnmodifiableNavigableSet<E> result = descendingSet;
            if (result == null) {
                result = descendingSet = new UnmodifiableNavigableSet<E>(delegate.descendingSet());
                result.descendingSet = this;
            }
            return result;
        }

        @Override
        public Iterator<E> descendingIterator() {
            return Iterators.unmodifiableIterator(delegate.descendingIterator());
        }

        @Override
        public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
            return unmodifiableNavigableSet(delegate.subSet(fromElement, fromInclusive, toElement, toInclusive));
        }

        @Override
        public NavigableSet<E> headSet(E toElement, boolean inclusive) {
            return unmodifiableNavigableSet(delegate.headSet(toElement, inclusive));
        }

        @Override
        public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
            return unmodifiableNavigableSet(delegate.tailSet(fromElement, inclusive));
        }

        private static final long serialVersionUID = 0;
    }

    /**
     * Returns a synchronized (thread-safe) navigable set backed by the specified navigable set. In
     * order to guarantee serial access, it is critical that <b>all</b> access to the backing
     * navigable set is accomplished through the returned navigable set (or its views).
     *
     * <p>
     * It is imperative that the user manually synchronize on the returned sorted set when iterating
     * over it or any of its {@code descendingSet}, {@code subSet}, {@code headSet}, or
     * {@code tailSet} views.
     * 
     * <pre>
     *    {@code
     *
     *   NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>());
     *    ...
     *   synchronized (set) {
     *     // Must be in the synchronized block
     *     Iterator<E> it = set.iterator();
     *     while (it.hasNext()) {
     *       foo(it.next());
     *     }
     *   }}
     * </pre>
     *
     * <p>
     * or:
     * 
     * <pre>
     *    {@code
     *
     *   NavigableSet<E> set = synchronizedNavigableSet(new TreeSet<E>());
     *   NavigableSet<E> set2 = set.descendingSet().headSet(foo);
     *    ...
     *   synchronized (set) { // Note: set, not set2!!!
     *     // Must be in the synchronized block
     *     Iterator<E> it = set2.descendingIterator();
     *     while (it.hasNext())
     *       foo(it.next());
     *     }
     *   }}
     * </pre>
     *
     * <p>
     * Failure to follow this advice may result in non-deterministic behavior.
     *
     * <p>
     * The returned navigable set will be serializable if the specified navigable set is
     * serializable.
     *
     * @param navigableSet the navigable set to be "wrapped" in a synchronized navigable set.
     * @return a synchronized view of the specified navigable set.
     * @since 13.0
     */
    @GwtIncompatible // NavigableSet
    public static <E> NavigableSet<E> synchronizedNavigableSet(NavigableSet<E> navigableSet) {
        return Synchronized.navigableSet(navigableSet);
    }

    /**
     * Remove each element in an iterable from a set.
     */
    static boolean removeAllImpl(Set<?> set, Iterator<?> iterator) {
        boolean changed = false;
        while (iterator.hasNext()) {
            changed |= set.remove(iterator.next());
        }
        return changed;
    }

    static boolean removeAllImpl(Set<?> set, Collection<?> collection) {
        checkNotNull(collection); // for GWT
        if (collection instanceof Multiset) {
            collection = ((Multiset<?>) collection).elementSet();
        }
        /*
         * AbstractSet.removeAll(List) has quadratic behavior if the list size is just less than the
         * set's size. We augment the test by assuming that sets have fast contains() performance,
         * and other collections don't. See
         * http://code.google.com/p/guava-libraries/issues/detail?id=1013
         */
        if (collection instanceof Set && collection.size() > set.size()) {
            return Iterators.removeAll(set.iterator(), collection);
        } else {
            return removeAllImpl(set, collection.iterator());
        }
    }

    @GwtIncompatible // NavigableSet
    static class DescendingSet<E> extends ForwardingNavigableSet<E> {
        private final NavigableSet<E> forward;

        DescendingSet(NavigableSet<E> forward) {
            this.forward = forward;
        }

        @Override
        protected NavigableSet<E> delegate() {
            return forward;
        }

        @Override
        public E lower(E e) {
            return forward.higher(e);
        }

        @Override
        public E floor(E e) {
            return forward.ceiling(e);
        }

        @Override
        public E ceiling(E e) {
            return forward.floor(e);
        }

        @Override
        public E higher(E e) {
            return forward.lower(e);
        }

        @Override
        public E pollFirst() {
            return forward.pollLast();
        }

        @Override
        public E pollLast() {
            return forward.pollFirst();
        }

        @Override
        public NavigableSet<E> descendingSet() {
            return forward;
        }

        @Override
        public Iterator<E> descendingIterator() {
            return forward.iterator();
        }

        @Override
        public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
            return forward.subSet(toElement, toInclusive, fromElement, fromInclusive).descendingSet();
        }

        @Override
        public NavigableSet<E> headSet(E toElement, boolean inclusive) {
            return forward.tailSet(toElement, inclusive).descendingSet();
        }

        @Override
        public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
            return forward.headSet(fromElement, inclusive).descendingSet();
        }

        @SuppressWarnings("unchecked")
        @Override
        public Comparator<? super E> comparator() {
            Comparator<? super E> forwardComparator = forward.comparator();
            if (forwardComparator == null) {
                return (Comparator) Ordering.natural().reverse();
            } else {
                return reverse(forwardComparator);
            }
        }

        // If we inline this, we get a javac error.
        private static <T> Ordering<T> reverse(Comparator<T> forward) {
            return Ordering.from(forward).reverse();
        }

        @Override
        public E first() {
            return forward.last();
        }

        @Override
        public SortedSet<E> headSet(E toElement) {
            return standardHeadSet(toElement);
        }

        @Override
        public E last() {
            return forward.first();
        }

        @Override
        public SortedSet<E> subSet(E fromElement, E toElement) {
            return standardSubSet(fromElement, toElement);
        }

        @Override
        public SortedSet<E> tailSet(E fromElement) {
            return standardTailSet(fromElement);
        }

        @Override
        public Iterator<E> iterator() {
            return forward.descendingIterator();
        }

        @Override
        public Object[] toArray() {
            return standardToArray();
        }

        @Override
        public <T> T[] toArray(T[] array) {
            return standardToArray(array);
        }

        @Override
        public String toString() {
            return standardToString();
        }
    }

    /**
     * Returns a view of the portion of {@code set} whose elements are contained by {@code range}.
     *
     * <p>
     * This method delegates to the appropriate methods of {@link NavigableSet} (namely
     * {@link NavigableSet#subSet(Object, boolean, Object, boolean) subSet()},
     * {@link NavigableSet#tailSet(Object, boolean) tailSet()}, and
     * {@link NavigableSet#headSet(Object, boolean) headSet()}) to actually construct the view.
     * Consult these methods for a full description of the returned view's behavior.
     *
     * <p>
     * <b>Warning:</b> {@code Range}s always represent a range of values using the values' natural
     * ordering. {@code NavigableSet} on the other hand can specify a custom ordering via a
     * {@link Comparator}, which can violate the natural ordering. Using this method (or in general
     * using {@code Range}) with unnaturally-ordered sets can lead to unexpected and undefined
     * behavior.
     *
     * @since 20.0
     */
    @Beta
    @GwtIncompatible // NavigableSet
    public static <K extends Comparable<? super K>> NavigableSet<K> subSet(NavigableSet<K> set, Range<K> range) {
        if (set.comparator() != null && set.comparator() != Ordering.natural() && range.hasLowerBound()
                && range.hasUpperBound()) {
            checkArgument(set.comparator().compare(range.lowerEndpoint(), range.upperEndpoint()) <= 0,
                    "set is using a custom comparator which is inconsistent with the natural ordering.");
        }
        if (range.hasLowerBound() && range.hasUpperBound()) {
            return set.subSet(range.lowerEndpoint(), range.lowerBoundType() == BoundType.CLOSED, range.upperEndpoint(),
                    range.upperBoundType() == BoundType.CLOSED);
        } else if (range.hasLowerBound()) {
            return set.tailSet(range.lowerEndpoint(), range.lowerBoundType() == BoundType.CLOSED);
        } else if (range.hasUpperBound()) {
            return set.headSet(range.upperEndpoint(), range.upperBoundType() == BoundType.CLOSED);
        }
        return checkNotNull(set);
    }
}
